﻿#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <stack>
#include <set>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};


//2115. 从给定原材料中找到所有可以做出的菜
//你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。
//第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，
//那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。
//同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。
//请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
//注意两道菜在它们的原材料中可能互相包含。
//示例 1：
//输入：recipes = ["bread"], ingredients = [["yeast", "flour"]], supplies = ["yeast", "flour", "corn"]
//输出：["bread"]
//解释：
//我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour"
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        vector<string> ret;
        int n = recipes.size();
        vector<bool> recordfalse(n, true);
        unordered_map<int, vector<int>> graph;
        unordered_set<string> sup{ supplies.begin(), supplies.end() };
        unordered_map<string, int> rec;
        for (int i = 0; i < n; ++i) {
            rec[recipes[i]] = i;
        }
        vector<int> recordin(n);
        for (int i = 0; i < n; ++i) {
            int count = 0, ingrenum = ingredients[i].size();
            for (auto& ingre : ingredients[i]) {
                if (sup.count(ingre)) {
                    count++;
                }
                if (rec.count(ingre)) {
                    //graph中的 sub1 : vec[sub2, sub3] 
                    //是指 recipes[sub2], recipes[sub3] 都至少需要recipes[sub1]才能完成
                    graph[rec[ingre]].push_back(i);
                    recordin[i]++;
                    count++;
                }
            }
            if (count != ingrenum) {
                recordfalse[i] = false;
            }
        }
        queue<int> startq;
        for (int i = 0; i < n; ++i) {
            if (recordin[i] == 0 && recordfalse[i] == true) {
                startq.push(i);
                ret.push_back(recipes[i]);
            }
        }
        while (!startq.empty()) {
            int frontsub = startq.front();
            startq.pop();
            for (int& sub : graph[frontsub]) {
                if (--recordin[sub] == 0) {
                    int count = 0, ingrenum = ingredients[sub].size();
                    for (auto& ingre : ingredients[sub]) {
                        if (sup.count(ingre)) {
                            count++;
                        }
                        if (rec.count(ingre) && recordfalse[rec[ingre]] == true) {
                            count++;
                        }
                    }
                    if (count == ingrenum) {
                        ret.push_back(recipes[sub]);
                        startq.push(sub);
                    }
                    else {
                        recordfalse[sub] = false;
                    }
                }
            }
        }
        return ret;
    }
};

//1711. 大餐计数
//大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
//你可以搭配 任意 两道餐品做一顿大餐。
//给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i​​​​​​​​​​​​​​ 道餐品的美味程度，
//返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。
//注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
//示例 1：
//输入：deliciousness = [1, 3, 5, 7, 9]
//输出：4
//解释：大餐的美味程度组合为(1, 3) 、(1, 7) 、(3, 5) 和(7, 9) 。
//它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂
class Solution {
#define MOD 1000000007
public:
    int countPairs(vector<int>& deliciousness) {
        // 枚举
        set<int> record{ deliciousness.begin(), deliciousness.end() };
        unordered_map<int, unsigned long long> ntotimes;
        for (auto& de : deliciousness) {
            ntotimes[de]++;
        }
        vector<int> deli{ record.begin(), record.end() };
        int n = deli.size();
        unsigned long long ret = 0;
        for (int i = 0; i < n; ++i) {
            long long curval = deli[i];
            for (int exp = 0; exp <= 21; ++exp) {
                long long sum = 1 << exp;
                if (sum - curval > curval && ntotimes.count(sum - curval)) {
                    ret += (ntotimes[sum - curval] % MOD) * (ntotimes[curval] % MOD);
                }
                else if (sum - curval == curval) {
                    ret += (ntotimes[curval] % MOD) * ((ntotimes[curval] - 1) % MOD) / 2;
                }
            }
        }
        return ret % MOD;
    }
};

//1679. K 和数对的最大数目
//给你一个整数数组 nums 和一个整数 k 。
//每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
//返回你可以对数组执行的最大操作数。
//示例 1：
//输入：nums = [1, 2, 3, 4], k = 5
//输出：2
//解释：开始时 nums = [1, 2, 3, 4]：
//- 移出 1 和 4 ，之后 nums = [2, 3]
//- 移出 2 和 3 ，之后 nums = []
//不再有和为 5 的数对，因此最多执行 2 次操作
class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        int n = nums.size();
        int ret = 0;
        unordered_map<int, int> ntotimes;
        for (int& num : nums) {
            ntotimes[num]++;
        }
        for (int i = 0; i < n; ++i) {
            // if(ntotimes.count(k - nums[i])){
            if (ntotimes.count(k - nums[i])) {
                if (k - nums[i] == nums[i]) {
                    if (ntotimes[nums[i]] >= 2) {
                        ret++;
                        ntotimes[nums[i]] -= 2;
                        if (ntotimes.count(nums[i]) == 0) {
                            ntotimes.erase(nums[i]);
                        }
                    }
                }
                else {
                    if (ntotimes[nums[i]] >= 1 && ntotimes[k - nums[i]] >= 1) {
                        ret++;
                        ntotimes[nums[i]]--;
                        if (ntotimes.count(nums[i]) == 0) {
                            ntotimes.erase(nums[i]);
                        }
                        ntotimes[k - nums[i]]--;
                        if (ntotimes.count(k - nums[i]) == 0) {
                            ntotimes.erase(k - nums[i]);
                        }
                    }
                }
            }
        }
        return ret;
    }
};
